﻿// ***********************************************************************
// Assembly         : Tx.OCC
// Author           : tianteng
// Created          : 03-09-2021
//
// Last Modified By : tianteng
// Last Modified On : 01-26-2021
// ***********************************************************************
// <copyright file="EarClippingTriangulator.cs" company="Tobias Schachte">
//     Copyright © 2015-2021 Tobias Schachte
// </copyright>
// <summary></summary>
// ***********************************************************************
using Occt;
using System;
using System.Collections.Generic;

namespace Tx.OCC
{
    /// <summary>
    /// Triangulates simple polygons (convex/concave, no holes) using
    /// the common Ear-Clipping algorithm. It works on a list of vertices
    /// and a ordered list of indices into the vertex list. The result
    /// is a list of indices for all triangles (3 indices per triangle).
    /// All triangles are returned in CCW order, regardless of the
    /// winding order of the polygon.
    /// 使用常见的剪耳算法对简单的多边形(凸/凹，无孔)进行三角形处理。它适用于顶点列表和顶点列表中的有序索引列表。结果是所有三角形的索引列表(每个三角形3个索引)。所有三角形都按CCW顺序返回，而不考虑多边形的缠绕顺序。
    /// </summary>
    public class EarClippingTriangulator
    {
        /// <summary>
        /// The point list
        /// </summary>
        List<gp_Pnt2d> _PointList;
        /// <summary>
        /// The index list
        /// </summary>
        List<int> _IndexList;



        /// <summary>
        /// Does the triangulation.
        /// </summary>
        /// <param name="vertexList">The vertex list.</param>
        /// <param name="indices">The indices.</param>
        /// <returns>List&lt;System.Int32&gt;.</returns>
//         public List<int> DoTriangulation(List<gp_Pnt> vertexList, IEnumerable<int> indices)
//         {
//             var resultIndices = new List<int>();
//             _IndexList = new List<int>(indices);
// 
//             Debug.Assert(vertexList.Count >= 3);
//             Debug.Assert(_IndexList.Count >= 3);
//             Debug.Assert(_IndexList.Max() < vertexList.Count);
//             Debug.Assert(_IndexList.Distinct().Count() == _IndexList.Count, "All indices of this polygon must point to a unique vertex!");
// 
//             // If last and first indices are identical, remove one
//             if (_IndexList[0] == _IndexList[_IndexList.Count - 1])
//                 _IndexList.RemoveAt(_IndexList.Count - 1);
// 
//             // Project vertices to common plane
//             if (!_CreateProjectedPointList(vertexList))
//                 return null;
// 
//             // Proceed until only one triangle left
//             while (_IndexList.Count > 3)
//             {
//                 var triangle = _FindEar();
// 
//                 // Create triangle
//                 resultIndices.Add(_IndexList[triangle.previous]);
//                 resultIndices.Add(_IndexList[triangle.index]);
//                 resultIndices.Add(_IndexList[triangle.next]);
// 
//                 // Remove index and point
//                 _IndexList.RemoveAt(triangle.index);
//                 _PointList.RemoveAt(triangle.index);
//             }
// 
//             // Copy last triangle
//             resultIndices.AddRange(_IndexList);
// 
//             return resultIndices;
//         }



        /// <summary>
        /// Creates the projected point list.
        /// </summary>
        /// <param name="vertexList">The vertex list.</param>
        /// <returns><c>true</c> if XXXX, <c>false</c> otherwise.</returns>
        bool _CreateProjectedPointList(List<gp_Pnt> vertexList)
        {
            _PointList = new List<gp_Pnt2d>(_IndexList.Count);

            var buildPlane = new GeomPlate_BuildAveragePlane(new TColgp_HArray1OfPnt(new TColgp_Array1OfPnt(vertexList)), vertexList.Count, 0, 1, 1);
            if (!buildPlane.IsPlane)
                return false;

            gp_Pln plane = buildPlane.Plane.Pln;
            //plane.Location = gp_Pnt.Origin;

            // Project points on plane
            double u = 0, v = 0;
            foreach (var i in _IndexList)
            {
                ElSLib.Parameters(plane, vertexList[i], out u, out v);
                _PointList.Add(new gp_Pnt2d(u, v));
            }

            // Get winding order of polygon
            double area = 0;
            for (int i = 0; i < _PointList.Count - 1; i++)
                area += _PointList[i].X * _PointList[i + 1].Y - _PointList[i + 1].X * _PointList[i].Y;
            if (area < 0)
            {
                _PointList.Reverse();
                _IndexList.Reverse();
            }

            return true;
        }



        /// <summary>
        /// Finds the ear.
        /// </summary>
        /// <returns>System.ValueTuple&lt;System.Int32, System.Int32, System.Int32&gt;.</returns>
//         (int previous, int index, int next) _FindEar()
//         {
//             for (int current = 0; current < _IndexList.Count; current++)
//             {
//                 // Catch vertices
//                 int previous = current == 0 ? _IndexList.Count - 1 : current - 1;
//                 int next = current == _IndexList.Count - 1 ? 0 : current + 1;
// 
//                 gp_Pnt2d a = _PointList[previous];
//                 gp_Pnt2d b = _PointList[current];
//                 gp_Pnt2d c = _PointList[next];
// 
//                 // If vertex is not convex, skip                
//                 if (_GetTriangleDirection(a, b, c) > 0)
//                     continue;
// 
//                 bool foundPointInTriangle = false;
//                 for (int i = 0; i < _IndexList.Count; i++)
//                 {
//                     if (i == current || i == previous || i == next)
//                         continue;
// 
//                     gp_Pnt2d s = _PointList[i];
// 
//                     // Point in triangle?
//                     if (_IsPointInTriangle(a, b, c, s))
//                     {
//                         foundPointInTriangle = true;
//                         break;
//                     }
//                 }
// 
//                 if (!foundPointInTriangle)
//                 {
//                     // We found an ear!
//                     return (previous, current, next);
//                 }
//             }
// 
//             return (0, 1, 2);
//         }



        /// <summary>
        /// Gets the triangle direction.
        /// </summary>
        /// <param name="a">a.</param>
        /// <param name="b">The b.</param>
        /// <param name="c">The c.</param>
        /// <returns>System.Int32.</returns>
        int _GetTriangleDirection(gp_Pnt2d a, gp_Pnt2d b, gp_Pnt2d c)
        {
            return Math.Sign(a.X * (c.Y - b.Y) + b.X * (a.Y - c.Y) + c.X * (b.Y - a.Y));
        }



        /// <summary>
        /// Determines whether [is point in triangle] [the specified a].
        /// </summary>
        /// <param name="a">a.</param>
        /// <param name="b">The b.</param>
        /// <param name="c">The c.</param>
        /// <param name="s">The s.</param>
        /// <returns><c>true</c> if [is point in triangle] [the specified a]; otherwise, <c>false</c>.</returns>
        bool _IsPointInTriangle(gp_Pnt2d a, gp_Pnt2d b, gp_Pnt2d c, gp_Pnt2d s)
        {
            bool __IsLeftOf(gp_Pnt2d p1, gp_Pnt2d p2)
            {
                return (p2.X - p1.X) * (s.Y - p1.Y) - (p2.Y - p1.Y) * (s.X - p1.X) >= 0;
            }

            return __IsLeftOf(a, b) && __IsLeftOf(b, c) && __IsLeftOf(c, a);
        }



    }
}